package leetcode.editor.cn;
//给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的
//数目来描述。 
//
// 返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
//输出：[2,11,7,15]
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
//输出：[24,32,8,12]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums1.length <= 105 
// nums2.length == nums1.length 
// 0 <= nums1[i], nums2[i] <= 109 
// 
// Related Topics 贪心 数组 双指针 排序 
// 👍 367 👎 0


import java.util.Arrays;
import java.util.PriorityQueue;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution62 {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int length = nums1.length;
        PriorityQueue<int[]> maxpq = new PriorityQueue<>(
                (int[] pq1, int[] pq2) -> {
                    return pq2[1] - pq1[1];
                });
        for (int i = 0; i < length; i++) {
            maxpq.offer(new int[]{i, nums2[i]});
        }
        Arrays.sort(nums1);
        int[] res = new int[length];
        // nums1[left] 是最小值，nums1[right] 是最大值
        int left = 0, right = length - 1;
        while (!maxpq.isEmpty()) {
            final int[] poll = maxpq.poll();
            int i = poll[0];
            int maxval = poll[1];
            if (maxval < nums1[right]) {
                // 如果 nums1[right] 能胜过 maxval，那就自己上
                res[i] = nums1[right];
                right--;
            } else {
                // 否则用最小值混一下，养精蓄锐
                res[i] = nums1[left];
                left++;
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
